"""
 * 200. 岛屿数量
 * 思路：题目要求返回连续在一起的岛屿数量，所以只要遇到“岛屿”，就去找他的上下左右四个点，如果是岛屿，将其“淹没”，同时将岛屿个数+1
 * 每个节点找它的上下左右4个节点，其实就相当于4叉树，层序遍历4叉树将岛屿淹没
"""
import collections
from typing import List


class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        count = 0

        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == '1':
                    count += 1
                    self.bfs(grid, i, j)

        return count

    def bfs(self, grid: List[List[str]], i: int, j: int):
        m = len(grid)
        n = len(grid[0])

        # 辅助队列(永远只存储一层节点)
        q = collections.deque()
        q.append(i * n + 1)
        grid[i][j] = '0'

        # 两个遍历，第一个遍历层数，第二个遍历每层的各个元素
        while q:
            # 控制节点数，保证每次while循环只取出一层
            size = len(q)

            for i in range(0, size):
                # 取出队列第一个元素
                cur = q.popleft()
                # 将当前节点的上下左右子节点存储到队列中，用于遍历下一层
                i = cur // n
                j = cur % n
                # 上
                if j > 0 and grid[i][j - 1] == '1':
                    q.append(i * n + (j - 1))
                    grid[i][j - 1] = '0'

                # 下
                if j < n - 1 and grid[i][j + 1] == '1':
                    q.append(i * n + (j + 1))
                    grid[i][j + 1] = '0'

                # 左
                if i > 0 and grid[i - 1][j] == '1':
                    q.append((i - 1) * n + j)
                    grid[i - 1][j] = '0'

                # 右
                if i < m - 1 and grid[i + 1][j] == '1':
                    q.append((i + 1) * n + j)
                    grid[i + 1][j] = '0'


if __name__ == '__main__':
    sl = Solution()
    nums = [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]]
    print(sl.numIslands(nums))
